package dp.最大正方形;

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return 0;
        }

        int height = matrix.length;
        int width = matrix[0].length;
        int maxSide = 0;

        // 每一个格子中的数表示该位置的最大边长
        int[][] dp = new int[height + 1][width + 1];
        
        for(int row = 0; row < height; row++) {
            for(int col = 0; col < width; col++) {
                if(matrix[row][col] == '1') {
                    dp[row + 1][col + 1] = Math.min(Math.min(dp[row][col], dp[row + 1][col]), dp[row][col + 1]) + 1;
                    maxSide = Math.max(maxSide, dp[row + 1][col + 1]);
                }
            }
        }

        return maxSide * maxSide;
    }
}